package 背包问题01;

import java.util.Scanner;

/**
 * @Date 2024/7/1 20:12
 * @description: 01背包模版题 (不必须装满 和 必须装满)
 * .    https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e
 * @Author LittleNight
 */
public class niuke41 {

        // int N = 1010, n, V; // 表示物品和体积
        int[][] dp;
        public static void main(String[] args) {
            int N = 1010;
            int n, V; // 表示物品个数和最多容纳的体积
            int[] v = new int[N]; // 表示体积
            int[] w = new int[N]; // 表示价值

            Scanner in = new Scanner(System.in);
            // 注意 hasNext 和 hasNextLine 的区别
            while (in.hasNextInt()) { // 注意 while 处理多个 case
                n = in.nextInt();
                V = in.nextInt();
                // 初始化. 注意是从1开始
                for (int i = 1; i <= n; i++) {
                    v[i] = in.nextInt();
                    w[i] = in.nextInt();
                }

                // 动态规划. 创建dp表, 初始化, 填表, 返回值
                // 第一问
                // 状态表示: 从前i个挑, 体积不超过j, 最大价值
                int[][] dp = new int[n + 1][V + 1];
                // int[][] dp = new int[N][N];
                for (int i = 1; i <= n; i++) {
                    // 没有进行初始化, j从 1 和 0 都对
                    // for (int j = 1; j <= V; j++) {
                    for (int j = 0; j <= V; j++) {
                        // 不选第i个位置, 这个一定是有的
                        dp[i][j] = dp[i - 1][j];
                        // 这个是有要求的
                        if (j - v[i] >= 0) {
                            dp[i][j] = Math.max(dp[i][j], w[i] + dp[i - 1][j - v[i]]);
                        }
                    }
                }
                // return dp[n][V];
                System.out.println(dp[n][V]);

                // 第二问, 需要进行初始化. 约定等于-1表示不能恰好装满背包
                for (int i = 0; i <= n; i++) {
                    for (int j = 0; j <= V; j++) {
                        dp[i][j] = 0;
                    }
                }
                // 这个主要填充一维数组
                // Arrays.fill(dp, 0);
                // Arrays.fill(dp, 0); // 初始化
                for (int j = 1; j <= V; j++) dp[0][j] = -1;
                for (int i = 1; i <= n; i++) {
                    // for (int j = 1; j <= V; j++) {
                    for (int j = 0; j <= V; j++) {
                        // 不选第i个位置, 这个一定是有的
                        dp[i][j] = dp[i - 1][j];
                        // 这个是有要求的
                        if (j - v[i] >= 0 && dp[i - 1][j - v[i]] != -1) {
                            dp[i][j] = Math.max(dp[i][j], w[i] + dp[i - 1][j - v[i]]);
                        }
                    }
                }
                int x = dp[n][V];
                System.out.println(x == -1 ? 0 : x);
            }
        }
    }

